\section{Base Configurations} \label{sec:base}
\noindent
Our idea to synthesize only selected configurations is based on the
observation that supporting execution for a set of \emph{base}
configurations is sufficient to cover all specified fault scenarios.
In this section, we illustrate this with a motivational example and a
formal classification of configurations. We further present an
algorithm to identify the set of base configurations. Last, we
describe a mapping approach that is performed for each base
configuration to develop a fault-tolerant control system.


\subsection{Motivational example} \label{sec:baseconfigexample}
\noindent
Let us consider our example in Figure~\ref{fig:systemexample}. Task
$\task_{11}$ reads sensors and $\task_{13}$ writes to actuators. Task
$\task_{12}$ does not perform input--output operations and can be
executed on any node in the platform. Sensors can be read by nodes
$\node_A$ and $\node_C$, whereas actuation can be performed only by
nodes $\node_C$ and $\node_D$. The mapping constraints for the tasks
are thus given by $\mappinglimitation(\task_{11}) = \{\node_A,
\node_C\}$, $\mappinglimitation(\task_{12}) = \nodeset$, and
$\mappinglimitation(\task_{13}) = \{\node_C, \node_D\}$.  First, let
us consider the initial scenario in which all computation nodes are
available and are executing one or several tasks each. The system is
thus in configuration $\nodeconfig_0 = \nodeset$ (see
Figure~\ref{fig:configurationdiagram}) and we assume that the actuator
task $\task_{13}$ executes on node $\node_C$ in this
configuration. Consider now that $\node_C$ fails and the system
reaches configuration $\nodeconfig_1 = \{\node_A, \node_B,
\node_D\}$. Task $\task_{13}$ must now execute on $\node_D$ in this
new configuration, since actuation can only be performed by nodes
$\node_C$ and $\node_D$. According to the mapping constraints given by
$\mappinglimitation$, there exists a possible mapping for each task in
configuration $\nodeconfig_1$; that is, it is possible to find a
mapping $\mapping_{\nodeconfig_1} : \taskset_\applicationset
\longrightarrow \nodeconfig_1$ such that
$\mapping_{\nodeconfig_1}(\task) \in \nodeconfig_1 \cap
\mappinglimitation(\task)$ for each $\task \in
\taskset_\applicationset$. We refer to such configurations as
\emph{feasible} configurations.  Thus, for a feasible configuration
and any task, there is at least one node in that configuration on
which the task can be mapped to.


If the system is in configuration $\nodeconfig_1$ and node $\node_A$
fails, we reach a new configuration $\nodeconfig_2 =
\{\node_B,\node_D\}$. Since task $\task_{11}$ cannot be mapped to any
node in the new configuration (i.e., $\mappinglimitation(\task_{11})
\cap \nodeconfig_2 = \emptyset$), we say that $\nodeconfig_2$ is an
\emph{unfeasible} configuration.  If, on the other hand, node
$\node_B$ fails in configuration $\nodeconfig_1$, the system reaches
configuration $\nodeconfig_3 = \{\node_A,\node_D\}$. In this
configuration, $\task_{11}$ and $\task_{13}$ must execute on $\node_A$
and $\node_D$, respectively. Task $\task_{12}$ may run on either
$\node_A$ or $\node_D$.  Thus, $\nodeconfig_3$ is a \emph{feasible}
configuration as it is possible to find map each task to a node that
is both available and allowed according to the given mapping
restrictions. We observe that if either of the nodes in
$\nodeconfig_3$ fails, the system reaches an unfeasible configuration.
We shall refer to configurations like $\nodeconfig_3$ as \emph{base}
configurations. Note that any configuration that is a superset of the
base configuration $\nodeconfig_3$ is a feasible configuration. By
considering the mapping constraints, we observe that the only other
base configuration in this example is $\{\node_C\}$. The set of base
configurations for our example system is thus $\baseconfigset = \{
\{\node_A,\node_D\}, \{\node_C\} \}$. Until this point of the example,
we did not consider any specification regarding the minimum number of
nodes that must be available in any situation. Thus, we assumed
implicitly that $\minimumavailablenodes = 1$, meaning that at least
one node must be available in any situation.  Typically, for large
systems with many nodes, it is not practical to require the system to
tolerate faults leading to configurations with only one available
node.  One reason is that one single node does not have the
computation power to execute all applications in the system. Another
reason is that it is not practical to assume that each node has
interfaces to all inputs and outputs of the plants (sensors and
actuators). Therefore, in addition to the mapping constraint
$\mappinglimitation$, the designer specifies a certain minimum number
of nodes that must be available. It is not of interest to support
execution in configurations with less number of nodes than this
specification.

Let us now assume that the designer specifies $\minimumavailablenodes
= 2$ (i.e., a minimum of two computation nodes will be always
available). This means that the system is not required to tolerate
node failures that lead to configurations with only one available
computation node. Thus, in this new context, configurations with one
computation node are unfeasible. This means that configuration
$\{\node_C\}$ is no longer a base configuration (it is now marked as
unfeasible), even though it satisfies the given mapping
constraints. Consequently, by studying the partial order in
Figure~\ref{fig:configurationdiagram}, we observe that the
configurations $\{\node_A,\node_C\}$, $\{\node_B,\node_C\}$, and
$\{\node_C,\node_D\}$ replace configuration $\{\node_C\}$ as base
configurations. Thus, by taking into account the mapping constraints
and the minimum number of computation nodes $\minimumavailablenodes =
2$ in a feasible configuration, we conclude that the set of base
configurations of our example system is
\begin{displaymath}
\baseconfigset =
\{
  \underbrace{
    \{\node_A,\node_C\}, 
    \{\node_B,\node_C\}, 
    \{\node_C,\node_D\}}_{\textrm{replace $\{\node_C\}$ for the case $\minimumavailablenodes=1$}},
  \{\node_A,\node_D\} 
\}.
\end{displaymath}
The configurations $\{\node_A,\node_B\}$ and $\{\node_B,\node_D\}$ are
unfeasible configurations due to the mapping constraints, whereas all
configurations with only one node are excluded and marked unfeasible
through the specified minimum number of available nodes
$\minimumavailablenodes = 2$.

It is important to note that the mapping for base configuration
$\{\node_A,\node_D\}$, including the produced schedule, task periods,
and control laws, can be used to operate the system in the feasible
configurations $\{\node_A,\node_B,\node_C,\node_D\}$,
$\{\node_A,\node_B,\node_D\}$, and $\{\node_A,\node_C,\node_D\}$.
This is done by merely using the two nodes in the base configuration
(i.e., $\node_A$ and $\node_D$), even though more nodes are available
in the mentioned feasible configurations. Although faults leading to
the mentioned feasible configurations can be tolerated by the fact
that execution is supported in all base configurations, the control
quality of the system can be improved if all computation nodes are
utilized to efficiently distribute the executions.  We shall discuss
this quality improvement in Section~\ref{sec:dse}.  By generating a
mapping (as well as customized schedules, periods, and control
laws~\cite{blind}) for each base configuration, and considering that
tasks are stored in the memory of the corresponding computation nodes
to realize the base configuration mappings, the system can tolerate
any sequence of node failures that lead the system to any feasible
configuration. Thus, a necessary and sufficient step in the design
phase, in terms of fault tolerance, is to identify the set of base
configurations and to generate a mapping of tasks to each such base
configuration. The remainder of this section is devoted to the
identification of base configurations and synthesis of their
corresponding task mappings.



\subsection{Classification of configurations}
\noindent
We consider that the mapping constraint $\mappinglimitation :
\taskset_\applicationset \longrightarrow \powerset{\nodeset}$ is given, meaning
that $\mappinglimitation(\task)$ defines the set of computation nodes
that task $\task \in \taskset_\applicationset$ may execute on.  The
designer further limits the execution of control applications to at
least $\minimumavailablenodes$ computation nodes. All other scenarios
are not required to be handled (such critical situations may be
handled by other means to provide safe operation with basic
functionality until the system is diagnosed and repaired).  Thus,
$\mappinglimitation$ and $\minimumavailablenodes$ decide directly the
set of configurations for which it is required to synthesize a
solution. Specifically, a given configuration $\nodeconfig \in
\configurationset$ is defined as a \emph{feasible} configuration if
$\setsize{\nodeconfig} \geqslant \minimumavailablenodes$ and
$\nodeconfig \cap \mappinglimitation(\task) \neq \emptyset$ for each
task $\task \in \taskset_\applicationset$. The set of feasible
configurations is denoted $\feasibleconfigset$.  

For an unfeasible configuration $\nodeconfig \in \configurationset
\setminus \feasibleconfigset$, there exists at least one task that due
to the given mapping constraints cannot execute on any computation
node in $\nodeconfig$ (i.e., $\nodeconfig \cap
\mappinglimitation(\task) = \emptyset$ for some $\task \in
\taskset_\applicationset$), or the number of available computation
nodes in that configuration is less than $\minimumavailablenodes$
(i.e., $\setsize{\nodeconfig} < \minimumavailablenodes$). 
A \emph{base configuration} $\nodeconfig$ is a feasible configuration
for which the failure of any computation node $\node \in \nodeconfig$
results in an unfeasible configuration $\nodeconfig \setminus \{ \node
\}$. The set of base configurations is thus defined as
\begin{displaymath}
\baseconfigset = \{ \nodeconfig \in
\feasibleconfigset : \nodeconfig \setminus \{\node\} \notin
\feasibleconfigset \textrm{ for any } \node \in \nodeconfig \}.
\end{displaymath}
The set of configurations $\configurationset = \powerset{\nodeset}$
(the powerset of $\nodeset$) is thus partitioned into disjoint sets of
feasible and unfeasible configurations. Some of the feasible
configurations form a set of base configurations, which represents the
boundary between the set of feasible and unfeasible configurations. As
we have discussed, to achieve fault tolerance, it is mandatory to
synthesize solutions that can be used to operate the system in all
base configurations. This enables the system to operate in any
feasible configuration.





\subsection{Identification of base configurations}
\noindent
A straightforward approach to find the set of base configurations is
to perform a search through the Hasse diagram of configurations.
Given the mapping constraint
$\mappinglimitation : \taskset_\applicationset \longrightarrow
\powerset{\nodeset}$ and the minimum number of available computation
nodes $\minimumavailablenodes$ in a configuration, we find the set of
base configurations $\baseconfigset$ based on a breadth-first
search~\cite{lewis91} of the Hasse diagram of configurations. The
search starts at the full configuration $\nodeset$ with
$\baseconfigset = \emptyset$ initially (it is assumed that $\nodeset$
is a feasible configuration). Let us consider an arbitrary visit of a
feasible configuration $\nodeconfig$ during any point of the
search. To determine whether or not to add $\nodeconfig$ to the set of
base configurations $\baseconfigset$, we consider each configuration
$\nodeconfig^\prime$ with $\setsize{\nodeconfig^\prime} =
\setsize{\nodeconfig} - 1$ (i.e., we consider the failure of any node
in $\nodeconfig$). If and only if at least one such
$\nodeconfig^\prime$ is unfeasible, we add $\nodeconfig$ to the set of
base configurations $\baseconfigset$.  Unfeasible configurations
$\nodeconfig^\prime$, as well as any unfeasible configuration
$\nodeconfig^\bis \subset \nodeconfig^\prime$, are not visited during
the search.

Due to the complexity of the Hasse diagram for systems with large
number of nodes, a breadth-first search starting from the full
configuration $\nodeset$ is practical only for relatively large values
of $\minimumavailablenodes$. If the minimum number of available nodes
$\minimumavailablenodes$ is relatively small, and the number of nodes
in the system is large, then the presented search method will visit
many configurations until the set of base configurations is found. Let
us therefore discuss an efficient alternative algorithm to construct
the set of base configurations $\baseconfigset$ from the mapping
constraint $\mappinglimitation : \taskset_\applicationset
\longrightarrow \powerset{\nodeset}$ and minimum number of available
nodes $\minimumavailablenodes$ directly. Without loss of generality,
we shall assume that the function $\mappinglimitation$ is injective
(i.e., $\mappinglimitation(\task_i) \neq \mappinglimitation(\task_j)$
for $\{\task_i\} \cap \{\task_j\} \neq \emptyset$). If this is not the
case, then, for the purpose of finding the set of base configurations,
it is an equivalent problem to study an injective function
$\mappinglimitation^\prime : \taskset_\applicationset^\prime
\longrightarrow \powerset{\nodeset}$ as a mapping constraint, where
$\taskset_\applicationset^\prime \subset
\taskset_\applicationset$. Further in that case, it is required that,
for each $\task \in \taskset_\applicationset \setminus
\taskset_\applicationset^\prime$, there exists exactly one
$\task^\prime \in \taskset_\applicationset^\prime$ for which
$\mappinglimitation(\task) = \mappinglimitation^\prime(\task^\prime)$.
Finally, in the following discussion, $\taskset_\applicationset^\prime$
and $\mappinglimitation^\prime$ replace $\taskset_\applicationset$ and
$\mappinglimitation$, respectively.


We construct the set of base configurations starting from the
tasks that have the most restrictive mapping constraints. Towards
this, let us consider a bijection $\ordering : \{ 1,\ldots,
\setsize{\taskset_\applicationset}\} \longrightarrow
\taskset_\applicationset$, where
$\setsize{\mappinglimitation(\ordering(k))} \leqslant
\setsize{\mappinglimitation(\ordering(k+1))}$ for $1 \leqslant k <
\setsize{\taskset_\applicationset}$.  The construction of the set of
base configurations $\baseconfigset$ is based on a function
$\configconstruct : \{1,\ldots,\setsize{\taskset_\applicationset}\}
\longrightarrow \powerset{\configurationset}$ that we shall define
with recursion.  For the base case, we define
\begin{displaymath}
  \configconstruct(1) = \bigcup_{\node \in
    \mappinglimitation(\ordering(1))} \{\node\}.
\end{displaymath}
Before we define $\configconstruct(k)$ for $1 < k \leqslant
\setsize{\taskset_\applicationset}$, let us define the function
$\feasibleconstruct : \configurationset \times
\{1,\ldots,\setsize{\taskset_\applicationset}\} \longrightarrow
\powerset{\configurationset}$ as $\feasibleconstruct(\nodeconfig,k) =
\{\nodeconfig\}$ if $\nodeconfig \cap \mappinglimitation(\ordering(k))
= \emptyset$ and
\begin{displaymath}
  \feasibleconstruct(\nodeconfig,k) =
  \bigcup_{\node \in \mappinglimitation(\ordering(k))} \nodeconfig \cup \{\node\}
\end{displaymath}
otherwise. If $\nodeconfig$ includes a node that task $\ordering(k)$
can execute on, then $\feasibleconstruct(\nodeconfig,k)$ does not add
additional nodes to $\nodeconfig$. If not, however, then
$\feasibleconstruct(\nodeconfig,k)$ extends $\nodeconfig$ in several
directions given by the set of nodes
$\mappinglimitation(\ordering(k))$ that task $\ordering(k)$ may
execute on. Now, we define recursively
\begin{displaymath}
  \configconstruct(k) = \bigcup_{\nodeconfig \in \configconstruct(k-1)}
  \feasibleconstruct(\nodeconfig,k)
\end{displaymath}
for $1 < k \leqslant \setsize{\taskset_\applicationset}$. The set
$\configconstruct(k)$ thus comprises configurations for which it is
possible to execute the tasks $\{\ordering(1), \ldots, \ordering(k)\}$
according to the mapping constraints induced by $\mappinglimitation$.
For the case of $\minimumavailablenodes = 1$, we know by construction
that $\baseconfigset \supseteq
\configconstruct(\setsize{\taskset_\applicationset})$ (we also know
that $\configconstruct(\setsize{\taskset_\applicationset})$ does not
contain unfeasible configurations). A pruning of the set
$\configconstruct(\setsize{\taskset_\applicationset})$ must therefore
be performed to identify feasible configurations
$\configconstruct(\setsize{\taskset_\applicationset}) \setminus
\baseconfigset$. This shall end our discussion regarding the
identification of the set $\baseconfigset$ for the case
$\minimumavailablenodes = 1$. For the general case
$\minimumavailablenodes > 1$, we first find the set $\baseconfigset$
for the special case $\minimumavailablenodes = 1$. Then, each element
$\nodeconfig \in \baseconfigset$ for which $\setsize{\nodeconfig} <
\minimumavailablenodes$ is replaced by the configurations in the set
\begin{displaymath}
  \left\{ \nodeconfig^\prime \in \configurationset :
  \textrm{$\nodeconfig \subseteq \nodeconfig^\prime$ and
    $\setsize{\nodeconfig^\prime} = \minimumavailablenodes$} \right\}.
\end{displaymath}







\subsection{Mapping} \label{sec:mapping}
\noindent
For each base configuration, we must map each task to an operational
node in that configuration. The task mappings for each base
configuration is synthesized at design time and is stored in the
memory of the computation nodes in the system. This step guarantees
that the system can tolerate faults that lead to any feasible
configuration by adapting to a task mapping of a base configuration at
runtime. Let us define the \emph{mapping} of the task set
$\taskset_\applicationset$ onto a feasible configuration $\nodeconfig
\in \feasibleconfigset$ as a function $\mapping_\nodeconfig :
\taskset_\applicationset \longrightarrow \nodeconfig$. For each task
$\task \in \taskset_\applicationset$, $\mapping_\nodeconfig(\task)$ is
the computation node that executes $\task$ when the system
configuration is $\nodeconfig$. It is required that the mapping
constraints are considered, meaning that
$\mapping_\nodeconfig(\task) \in \mappinglimitation(\task)$ for each
$\task \in \taskset_\applicationset$.

For a given configuration $\nodeconfig \in \feasibleconfigset$ and
mapping $\mapping_\nodeconfig : \taskset_\applicationset
\longrightarrow \nodeconfig$, we have developed an integrated control
and scheduling framework for distributed embedded systems~\cite{blind}.
The parameters that are synthesized are
\begin{compactitem}
  \item the period of each control application,
  \item the control law for each control application $\application_i$
    to compute the control signal $\plantinput_i$ based on the
    measured plant outputs $\plantoutput_i$, and
  \item the execution and communication schedule for all tasks and
    messages in the system, respectively.
\end{compactitem}
The objective is to minimize the overall control cost
\begin{equation}
  \controlcost =
  \sum_{i \in \indexset_\plants} \controlcost_i,
  \label{eq:overallcontrolcost}
\end{equation}
which indicates maximization of the total control quality of the
system. The period selection is performed with genetic
algorithms~\cite{heuristic}, whereas the construction of the schedule
and control law is driven by the delay characteristics and control
quality. We have extended the genetic algorithm to also optimize task
mapping. The mapping affects the delay characteristics indirectly
through task and message scheduling. It is thus of great importance to
optimize task mapping, schedules, and control laws to achieve a
customized solution with high control quality in a given
configuration. Thus, for a given $\nodeconfig \in \feasibleconfigset$,
we shall use our tool to find a customized mapping
$\mapping_\nodeconfig : \taskset_\applicationset \longrightarrow
\nodeconfig$ together with a schedule and controllers (periods and
control laws). The mapping is constructed to satisfy the mapping
constraints (i.e., $\mapping_\nodeconfig(\task) \in
\mappinglimitation(\task)$ for each $\task \in
\taskset_\applicationset$) and with the objective to minimize the
total control cost given by Equation~\ref{eq:overallcontrolcost}. We
denote with $\mem_d^\nodeconfig$ the amount of memory required on node
$\node_d$ ($d \in \indexset_\nodeset$) to store information related to
the schedule, periods, and control laws that are customized for
configuration $\nodeconfig$. This memory consumption is given as an
output of the synthesis step~\cite{blind}.  Further, for each base
configuration $\nodeconfig \in \baseconfigset$, we consider that each
node $\node \in \nodeconfig$ stores all tasks $\task \in
\taskset_\applicationset$ for which $\mapping_\nodeconfig(\task) =
\node$ (i.e., we consider that tasks are preinstalled on nodes to
realize mappings for base configurations).
